package org.example.sword2offer.primary;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @author: lynn
 * @Descript:  NC70 给定一个无序单链表，实现单链表的排序(按升序排序)。
 * @date: 2021/7/7 18:33
 * @version: 1.0
 */
public class Q85_SortListNode {
    public static void main(String[] args) {
        // 1,3,2,4,5,19,7,9,8
        ListNode listNode=new ListNode(1);
        listNode.next=new ListNode(3);
        listNode.next.next=new ListNode(2);
        listNode.next.next.next=new ListNode(4);
        listNode.next.next.next.next=new ListNode(5);
        listNode.next.next.next.next.next=new ListNode(19);
        listNode.next.next.next.next.next.next=new ListNode(7);
        listNode.next.next.next.next.next.next.next=new ListNode(9);
        listNode.next.next.next.next.next.next.next.next=new ListNode(8);
        Q85_SortListNode sortListNode=new Q85_SortListNode();
        sortListNode.sortInList(listNode);
        System.out.println("xxxxx");
    }

    public ListNode sortInList (ListNode head) { //fixme NC70  给定一个无序单链表，实现单链表的排序(按升序排序)
        // write code here
        List<ListNode> list=new ArrayList();
        if (head==null){
            return null;
        }
        while (head!=null){ //fixme 遍历链表
            list.add(head);
            head=head.next;
        }
        Collections.sort(list,(l1, l2)->{
            return l1.val-l2.val;
        });
        head=list.get(0);
        for (int i = 0; i <list.size() ; i++) {
            if (i+1<list.size()){
                list.get(i).next=list.get(i+1);
            }else {
                list.get(i).next=null; //fixme 必须为空否则会导致环形链表
            }
        }
        return  head;
    }
    public static class ListNode{
        ListNode next;
        int val;
        ListNode(int val){
            this.val=val;
        }
    }
}
